package F.树;



import java.util.LinkedList;
import java.util.Queue;

public class _101_对称二叉树 {
    /**
     * 自解思路：递归法 如果左右子树都是对称 再判断这左右节点
     * ---错误的：左右各对称 但不一定他们对称
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {

        if (root == null){
            return true;
        }

        if (root.left == null && root.right==null){
            return true;
        }else if (root.left != null && root.right!=null){
            if ( !isSymmetric(root.left) || !isSymmetric(root.right)) {
                return false;
            }
            if (root.right.val == root.left.val){
                return true;
            }
        }


        return false;
    }

    /**
     * 题解：递归法--两个指针进行迭代 一个左移 一个右移
     * 因为两个指针 所以得新写一个迭代方法
     *
     */
    public boolean isSymmetric1(TreeNode root) {
        return check(root,root);
    }
    public boolean check(TreeNode p,TreeNode q){
        if (p == null && q == null){
            return true;
        }
        if  (p == null || q == null){
            return false;
        }

        return p.val == q.val && check(p.right,q.left)  && check(p.left,q.right);
    }

    /**
     * 迭代法：根据递归法更改--时间比较长
     * 引入队列 一层一层放入 两个根结点
     */
    public boolean isSymmetric2(TreeNode root) {
        return check1(root,root);
    }
    public boolean check1(TreeNode p,TreeNode q){
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(p);
        queue.add(q);

        while (!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();

            if (p == null && q== null){
                continue;
            }
            //上面这个if 是为了排除下面或操作的同为1 的情况 同时跳过加点的操作
            if (p == null || q== null || p.val != q.val){
                return false;
            }

            //添加孩子结点
            queue.add(p.left);
            queue.add(q.right);

            queue.add(p.right);
            queue.add(q.left);

        }

        return  true;

    }
}
